nclude"Heap.h"
//初始化堆
void HeapInit(HP* php)
{
    assert(php);
    php->a = NULL;
    php->size = php->capacity = 0;
}
 
//堆的销毁
void HeapDestroy(HP* php)
{
    assert(php);
    free(php->a);
    php->a = NULL; //置空
    php->size = php->capacity = 0; //置0
}
//堆的打印
void HeapPrint(HP* php)
{
    assert(php);
    for (size_t i = 0; i < php->size; i++)
    {
        printf("%d ", php->a[i]);
    }
    printf("\n");
}
 
//交换
void Swap(HPDataType* pa, HPDataType* pb)
{
    HPDataType tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}
 
//向上调整算法
void AdjustUp(HPDataType* a, size_t child)
{
    size_t parent = (child - 1) / 2;
    while (child > 0)
    {
        //if (a[child] > a[parent]) //大根堆
        if (a[child] < a[parent]) //小根堆
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
 
//向下调整算法
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
    int parent = root;
    int child = 2 * parent + 1;
    while (child < size)
    {
        //1、确保child的下标对应的值最小，即取左右孩子较小那个
        if (child + 1 < size && a[child + 1] < a[child]) //得确保右孩子存在
        {
            child++; //此时右孩子小
        }
        //2、如果孩子小于父亲则交换，并继续往下调整
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}
 
//堆的插入
void HeapPush(HP* php, HPDataType x)
{
    assert(php);
    //检测是否需要扩容
    if (php->size == php->capacity)
    {
        //扩容
        size_t newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newcapacity;
    }
    php->a[php->size] = x;
    php->size++;
    //保持继续是堆，向上调整算法
    AdjustUp(php->a, php->size - 1);
}
 
 
//堆的删除  删除堆顶的数据
void HeapPop(HP* php)
{
    assert(php);
    assert(php->size > 0);//确保size>0
    Swap(&php->a[0], &php->a[php->size - 1]); //交换堆头和堆尾
    php->size--;
    //向下调整，确保仍然是堆结构
    AdjustDown(php->a, php->size, 0);
}
 
 
//堆的判空
bool HeapEmpty(HP* php)
{
    assert(php);
    return php->size == 0; //size为0即为空
}
 
//堆的元素个数
size_t HeapSize(HP* php)
{
    assert(php);
    return php->size;
}
 
//获取堆顶元素
HPDataType HeapTop(HP* php)
{
    assert(php);
    assert(php->size > 0);
    return php->a[0];
}
//堆排序
void HeapSort(int*a,int n)
{
 
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }
 
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
    
}

